/*
 * Copyright (c) 2021
 * User:LENOVO
 * File:接雨水.java
 * Date:2021/02/18 14:18:18
 */

package org.bytedance.数组与排序;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 */
public class 接雨水 {


    public static void main(String[] args) {
        int[] inputs = new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        接雨水 instance = new 接雨水();
        int i = instance.trap2(inputs);
        System.out.println(i);
        i = instance.trap(inputs);
        System.out.println(i);
        inputs = new int[]{4, 2, 0, 3, 2, 5};
        i = instance.trap(inputs);
        System.out.println(i);
        i = instance.trap2(inputs);
        System.out.println(i);
    }


    /**
     * 使用栈
     *
     * @param height
     * @return
     */
    public int trap2(int[] height) {
        int res = 0, current = 0;
        Deque<Integer> stack = new LinkedList<>();
        while (current < height.length) {
            while (!stack.isEmpty() && height[current] > height[stack.peek()]) {
                int top = stack.pop();
                if (stack.isEmpty()) break;
                int distance = current - stack.peek() - 1;
                int bound_height = Math.min(height[current], height[stack.peek()]) - height[top];
                res += distance * bound_height;
            }
            stack.push(current++);
        }
        return res;
    }


    /**
     * 双指针
     *
     * @param height
     * @return
     */
    public int trap(int[] height) {
        int left = 0, right = height.length - 1;
        int res = 0;
        int left_max = 0, right_max = 0;
        while (left < right) {
            if (height[left] < height[right]) {
                if (height[left] >= left_max) {
                    left_max = height[left];
                } else {
                    res += (left_max - height[left]);
                }
                ++left;
            } else {
                if (height[right] >= right_max) {
                    right_max = height[right];
                } else {
                    res += (right_max - height[right]);
                }
                --right;
            }
        }
        return res;

    }

}
